package leetcode;

import java.util.*;

/**
 * Created by tiang on 2018/9/5.
 */
public class WordLadderII {
    private List<String> isOneOrLessAway(String word, Set<String> words){
        List<String> res = new ArrayList<>();
        char [] cur = word.toCharArray();
        for(int i = 0; i<cur.length;++i ){
            char original = cur[i];
            for(int j=(int)'a'; j<=(int)'z';++j){
                if((char)j!=original){
                    cur[i]=(char)j;
                    if(words.contains(String.valueOf(cur))){
                        res.add(String.valueOf(cur));
                    }
                }
            }
            cur[i]=original;
        }
        return res;
    }
    class ladder{
        String word;
        int depth;
        public ladder(int depth, String word){
            this.word=word;
            this.depth = depth;
        }
    }
    private void dfs(List<List<String>> res, List<String> cur, Map<String,Set<String>> children, String nextWord, String endWord, int foundDepth){
        if(nextWord.equals(endWord) && cur.size()==foundDepth){
            res.add(new ArrayList<>(cur));
            return;
        }
        if(cur.size()>foundDepth){
            return;
        }
        Set<String> childs = children.get(nextWord);
        if(childs==null)return;
        for(String child: childs){
            cur.add(child);
            dfs(res,cur,children,child,endWord,foundDepth);
            //backtrack
            cur.remove(cur.size()-1);
        }
    }
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Map<String,Integer> visited= new HashMap<>();
        Map<String,Set<String>> children = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        Queue<ladder> bfs = new LinkedList<>();
        bfs.add(new ladder(1,beginWord));
        int foundDepth = Integer.MAX_VALUE;
        Set<String> wordsLeft = new HashSet<>(wordList);
        wordsLeft.remove(beginWord);
        visited.put(beginWord,1);
        while(!bfs.isEmpty()){
            ladder next = bfs.remove();
            String str = next.word;
            int depth = next.depth;
            wordsLeft.remove(str);
            if(str.equals(endWord)){
                foundDepth=depth;
                break;
            }
            Set<String> childs = children.get(str);
            if(childs==null)childs=new HashSet<>();
            List<String> findWords = isOneOrLessAway(str,wordsLeft);
            for(int i=0; i<findWords.size();++i){
                if(!visited.containsKey(findWords.get(i))||findWords.get(i).equals(endWord)){
                    visited.put(findWords.get(i),depth+1);
                    childs.add(findWords.get(i));
                    bfs.add(new ladder(depth+1,findWords.get(i)));
                }
                else if(visited.get(findWords.get(i))==depth+1){
                    //don't repeat add to the bfs queue
                    childs.add(findWords.get(i));
                }
            }
            findWords.add(str);
            children.put(str,childs);
        }
        List<String> cur = new ArrayList<>();
        cur.add(beginWord);
        dfs(result,cur,children,beginWord,endWord,foundDepth);
        return result;
    }
}
